package 二分查找;

/**
 * 153. 寻找旋转排序数组中的最小值
 *
 * 思路：还是采用二分查找的思路，利用数组的有序性进行查找。
 * 解题思路：
 *  1：旋转数组特性：旋转后的数组分为两个递增子数组，且右子数组的所有元素均小于左子数组。最小值位于右子数组的第一个元素。
 *  2：二分查找策略：
 *      比较中间元素nums[mid]与右边界元素nums[right]。
 *      如果nums[mid] > nums[right]，说明最小值在右半部分，调整左边界left = mid + 1。
 *      否则，最小值在左半部分或中间位置，调整右边界right = mid。
 *  3：终止条件：
 *      终止条件：当left == right时，找到最小值。
 */
public class L_153 {

    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right){
            int mid = left + (right - left) / 2;
            // 证明最小值在右半部分
            if (nums[mid] > nums[right]){
                left = mid + 1;
            }else { // 最小值在左半部分或者中间位置
                right = mid;
            }
        }
        // 返回最左边的值
        return nums[left];
    }
}
